﻿using System;

namespace binarytree_test {
    class Program {
        static void Main (string[] args) {
            BinaryTree<int> mybinaryTree = new BinaryTree<int> ();

            mybinaryTree.Insert (10);
            mybinaryTree.Insert (7);
            mybinaryTree.Insert (6);
            mybinaryTree.Insert (8);
            mybinaryTree.Insert (12);
            mybinaryTree.Insert (24);
            mybinaryTree.Insert (15);

            Console.WriteLine (mybinaryTree);
        }
    }
    public class TreeNode<T> {
        public int data { get; set; }
        public TreeNode<T> LeftNode { get; set; }
        public TreeNode<T> RightNode { get; set; }
        public TreeNode<T> ParentNode { get; set; }
        public TreeNode () {
            this.data = 0;
            this.LeftNode = null;
            this.RightNode = null;
            this.ParentNode = null;
        }
    }
    public class BinaryTree<T> {
        public TreeNode<T> root;
        public BinaryTree () {
            root = null;
        }
        public bool IsEmpty () {
            if (root == null) {
                return true;
            }
            return false;
        }
        public void Insert (int data) {
            if (root == null) {
                root = new TreeNode<T> ();
                root.data = data;
                root.LeftNode = null;
                root.RightNode = null;
                root.ParentNode = null;
            } else {
                Insert (root, data);
            }
        }
        /// <summary>
        /// 插入结点,利用递归算法
        /// </summary>
        /// <param name="treeNode">代表要插入的结点</param>
        /// <param name="data">代表插入结点的数据</param>
        private void Insert (TreeNode<T> root_l, int data) {
            if (data == root_l.data) {
                Console.WriteLine ("插入失败，数据重复");
                return;
            } else if (data < root_l.data) {
                if (root_l.LeftNode == null) {
                    TreeNode<T> temp = new TreeNode<T> ();
                    temp.data = data;
                    temp.ParentNode = root_l;

                    root_l.LeftNode = temp;
                } else {
                    Insert (root_l.LeftNode, data);
                }
            } else if (data > root_l.data) {
                if (root_l.RightNode == null) {
                    TreeNode<T> temp = new TreeNode<T> ();
                    temp.data = data;
                    
                    temp.ParentNode = root_l;

                    root_l.RightNode = temp;
                } else {
                    Insert (root_l.RightNode, data);
                }
            }
        }
        public void Search (int data) {
            TreeNode<T> searchNode = new TreeNode<T> ();

        }
        private TreeNode<T> Search (TreeNode<T> root, int data) {
            TreeNode<T> temp = new TreeNode<T> ();
            if (root.data == data) {
                Console.WriteLine ("成功找到：" + data);
                return root;
            } else if (root.data < data) {
                if (root.RightNode != null) {
                    temp = root.RightNode;
                    Search (temp, data);
                }
            } else if (root.data > data) {
                if (root.LeftNode != null) {
                    temp = root.LeftNode;
                    Search (temp, data);
                }
            } else {
                Console.WriteLine ("当前树种不存在这样的结点");
                return null;
            }
            return temp;
        }
    }
}